package demo5;


import java.util.*;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class T {
    static class StrNum {
        public String str;
        public Integer count;

        public StrNum() {
        }

        public StrNum(String str, Integer count) {
            this.str = str;
            this.count = count;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            StrNum strNum = (StrNum) o;
            return Objects.equals(str, strNum.str);
        }

        @Override
        public int hashCode() {
            return Objects.hash(str);
        }
    }
    public List<String> topKFrequent(String[] words, int k) {
        if(k >= words.length) {
            return createList(words, k);
        }

        Map<String, StrNum> map = new HashMap<>();
        for(String word : words) {
            if(map.get(word) != null) {
                map.get(word).count++;
            } else {
                map.put(word, new StrNum(word, 1));
            }
        }

        PriorityQueue<StrNum> queue = new PriorityQueue<>((o1, o2) -> {
            int compare = o1.count.compareTo(o2.count);
            return compare != 0 ? compare : o2.str.compareTo(o1.str);
        });
        for(Map.Entry<String, StrNum> entry : map.entrySet()) {
            StrNum value = entry.getValue();
            if(queue.size() < k) {
                queue.offer(value);
            } else {
                StrNum peek = queue.peek();
                if(value.count.compareTo(peek.count) > 0) {
                    queue.poll();
                    queue.offer(value);
                } else if (value.count.compareTo(peek.count) == 0 &&
                        value.str.compareTo(peek.str) < 0) {
                    queue.poll();
                    queue.offer(value);
                }
            }
        }

        List<String> list = new LinkedList<>();
        while(!queue.isEmpty()) {
            list.add(queue.poll().str);
        }
        return list;
    }
    private List<String> createList(String[] words, int len) {
        List<String> list = new LinkedList<>();
        for (int i = 0; i < len && i < words.length; i++) {
            list.add(words[i]);
        }
        return list;
    }
}
